package tree.Huffman;

import java.sql.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTree {
    private ArrayList<Node> arrayList;
    public HuffmanTree(int[] list) {
        //接收一个数组,将其转成list集合,方便排序
        arrayList = new ArrayList<>();
        for(int num:list){
            arrayList.add(new Node(num));
        }
       while(arrayList.size()>1){
           Collections.sort(arrayList);

           show(arrayList);
           Node leftNode=arrayList.get(0);
           Node rightNode=arrayList.get(1);

           Node parent = new Node(leftNode.value+rightNode.value);
           parent.leftNode=leftNode;
           parent.rightNode=rightNode;


           arrayList.remove(leftNode);
           arrayList.remove(rightNode);
           arrayList.add(parent);
       }

    }

    public Node getRoot(){
         return arrayList.get(0);
    }







    public void show(List<Node> list){
        for(Node node:list){
            System.out.print(node+"  ");
        }
        System.out.println();
    }
}
class Node implements Comparable{
    int value;
    Node leftNode;
    Node rightNode;
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    public Node(int value) {
        this.value = value;
    }

    @Override
    public int compareTo(Object o) {
        //当前对象较大时,返回正整数
        Node node=(Node)o;
        return this.value-node.value;
    }
    public void preTravel(Node root){
        if (root==null){
            System.out.println("树为空");
            return;
        }
        System.out.println(root);
        if (root.leftNode!=null){
            preTravel(root.leftNode);
        }
        if (root.rightNode!=null){
            preTravel(root.rightNode);
        }
    }
}